package com.cheng.learn.leetcode;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @description: 二叉树的序列化和反序列化
 * @author: ChengHaiZhu
 * @create: 2021-03-21 22:08
 **/
public class Codec297 {
    /**
     * 二叉树的序列化方法
     * @param root
     * @return
     */
    public String serialize(TreeNode root) {
        StringBuilder ans = new StringBuilder();
        getAns(ans,root);
        return ans.toString();
    }

    /**
     * 层序遍历二叉树
     * @param ans
     * @param root
     */
    public void getAns(StringBuilder ans,TreeNode root){
        if(root == null){
            ans.append("null,");
            return;
        }
        ans.append(root.val + ",");
        getAns(ans,root.left);
        getAns(ans,root.right);
    }

    /**
     * 二叉树的反序列化方法
     * @param data
     * @return
     */
    public TreeNode deserialize(String data) {
        Queue<String> queue = new LinkedList<>(Arrays.asList(data.split(",")));
        return dfs(queue);
    }

    /**
     * 深度优先算法放数据
     * @param queue
     * @return
     */
    private TreeNode dfs(Queue<String> queue) {
        String val = queue.poll();
        if("null".equals(val)){
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(val));
        root.left = dfs(queue);
        root.right = dfs(queue);
        return root;
    }

    // 定义私有化二叉树内部类
    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}


